1. Field of the Invention
The present invention relates to the generation of error detections code words, and more particularly to the generation of cyclic redundancy check (CRC) code words.
2. Description of the Related Art
In digital data transmission systems a sequence of binary information is delivered to a receiver across a transmission channel. Due to interference or impairments in the transmission channel, the binary data may be corrupted or changed while en route to a receiver. For this reason, error detection schemes are commonly employed to detect any differences between the originally transmitted data bits and the received data bits. In order to implement an error detection scheme, the bit stream that is transmitted is divided into a series of frame, each frame having a known group of bits. The frames can be of fixed or variable length, but in any case the receiver of the transmission can recover the frame boundaries. An error detection scheme then operates frame by frame.
Cyclic redundancy check (CRC) is a technique for error checking in data that has been transmitted by a digital data transmission system. It is often used as an error detection scheme because it is easy to implement and can detect a large class of errors. CRC is a checksum algorithm based on modulo-2 binary division.
The mathematics underlying CRC is known to those skilled in the art of error control coding and is described in detail in “Error Control Coding: An Introduction,” by Peter Sweeney, Prentice Hall 1991, as well as in “Theory and Practice of Error Control Codes.” by Richard E. Blahut, Addison-Wesley Publishing Company. Inc. 1983, which are hereby incorporated by reference, as if fully set forth herein.
The transmitter determines the CRC of a given frame by interpreting the data bits in the frame to be the coefficients of a binary field polynomial. For example, if there are K bits in a frame then the bits in the message are CK-1, CK-2, CK-3, . . . C2, C1, C0, where CK-1 is the first bit in the frame (transmitted first in time) and C0 the last bit in the frame (transmitted last), each having a binary value of 1 or 0. This frame can thus be represented as a (K−1)th order binary field polynomial:C(X)=CK-1XK-1+CK-2XK-2+ . . . +C2X2+C1X+C0;
wherein, X is a bit delay operator and the C1's are the coefficients of the polynomial.
R zero bits are then appended to the frame creating an augmented frame with N=K+R bits. Appending R zeros to the frame is mathematically equivalent to multiplying the polynomial by XR. The augmented polynomial is now C(X)*XR, hence becoming a polynomial of the order (N−1)th.
The CRC of the augmented frame is calculated by dividing C(X)*XR by a binary field polynomial of order R, G(X) known as the generator polynomial. The remainder of the polynomial division is another polynomial of order R−1, represented by R bits. Appending the bits to the original non-augmented frame is mathematically equivalent to adding the remainder to the augmented polynomial, forming a transmitted polynomialT(X)=C(X)*XR+((C(X)*XR) modulo G(X)).
The calculated CRC can be used to detect if errors occurred in the received data. The receiver receives the N bit frame, treats the bits as the coefficients of an (N−1)th order polynomial and divides this polynomial by the generator polynomial. The remainder of this division will be zero if no errors occurred during transmission. Both the transmitter and receiver must perform polynomial division.
The following is an example of the CRC process applied on the following parameters: the original frame (message) to be transmitted (M), is ten bits long and equals to “1010001101”. The remainder (R), i.e., the CRC code to be appended to M, is five bits long. The generator polynomial (G) is a 5th degree polynomial, for example the following may be used:G(X)=X5+X4+X2+1;
The binary representation of G(X) is “110101”. The CRC process is as follows: first, adding to M five zeros and the divide by G, i.e. performing   101000110100000  110111
The reminder, which is 1110, is appended to M. Therefore the resulting frame to be transmitted (T) equals to 1010001101 1110.
Reference is now made to FIG. 1 where an exemplary prior art CRC machine 100 is shown. CRC machine 100 uses registers 110-1 through 110-8 with feedback to implement the division of a frame of bits by an example generator polynomial:
 G(X)=X8+X6+X4X+X2+1
Registers 110-1 through 110-8 are capable of performing delays of 1 bit per clock cycle. XOR logic gates 120 before registers 110-1, 110-2, 110-4, and 110-6 correspond to the non-zero coefficients of the G(X) divisor polynomial. Namely, the presence or the absence of a XOR gate corresponds to the presence or absence of a term in the generator polynomial G(X). Registers 110-1 through 110-8 would typically be initialized to the first eight bits of the input data stream that is CN-1 to CN-8 at the start of the polynomial division. Alternatively, the remainder can be initialized to zero and CRC machine 100 may be clocked an additional eight times to shift the first eight bits of the input data stream. Then, the frame bits are shifted at each iteration into the circuitry in the order CN-9, CN-10, CN-11, CN-12, . . . C1, C0. At the end of the iterations, registers 110-1 through 110-8 contain the final remainder, which is shifted out as the CRC (at the transmitter) or used to determine if errors occurred (at the receiver). The number of iterations is equal to the frame length plus another 9 zeros (the number of zeros equivalent to the polynomial order).
The CRC checksum result is valid after a fixed delay from the time the last bit of the original input data stream was inserted to CRC machine. This fixed delay corresponds to the number of registers, which in turn corresponds with the order of the CRC. This delay deteriorates the efficiency of data transfer. The delay is caused by the sequence of zeroes, corresponding to the CRC order, that are appended to the data bits being transmitted and inserted to the CRC machine as required according to the CRC processing algorithms.
Therefore, there is thus a widely recognized need for and it would be advantageous to provide a method and apparatus that would calculate the CRC code immediately after the last bit of data is inserted into the CRC machine. That is, the provided apparatus would calculate the CRC without the insertion of the series of zeros and hence avoid the associated delay.